package club.xiaojiawei.back;

import java.util.*;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/22/22 4:56 PM
 * @question 332. 重新安排行程
 * @description 给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
 * 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
 * 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
 * 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次
 */
public class FindItinerary332 {

    public static void main(String[] args) {
        System.out.println("AXA".compareTo("ANU"));
        FindItinerary332 test = new FindItinerary332();
        System.out.println(test.findItinerary2(List.of(
                List.of("JFK","ABC"), List.of("JFK", "SJC"), List.of("SJC", "JFK")
        )));
    }

    /**
     * HashMap+递归
     * @param tickets
     * @return
     */
    public List<String> findItinerary(List<List<String>> tickets) {
        HashMap<String, List<String[]>> map = new HashMap<>();
        for (List<String> ticket : tickets) {
            List<String[]> temp = map.getOrDefault(ticket.get(0), new ArrayList<>());
            temp.add(new String[]{ticket.get(1), "f"});
            map.put(ticket.get(0), temp);
        }
        map.forEach((k, v) -> v.sort((Comparator.comparing(o -> o[0]))));
        this.length = tickets.size();
        choose.add("JFK");
        recursion("JFK", map, 0);
        return result;
    }

    public boolean recursion(String from, HashMap<String, List<String[]>> map, int count){
        if (count == length){
            result = new ArrayList<>(choose);
            return true;
        }
        count++;
        List<String[]> temp = map.get(from);
        if (temp == null){
            return false;
        }
        for (String[] s : temp) {
            if (s[1].equals("t")){
                continue;
            }
            choose.add(s[0]);
            s[1] = "t";
            if (recursion(s[0], map, count)){
                return true;
            }
            s[1] = "f";
            choose.remove(choose.size() - 1);
        }
        return false;
    }

    int length = 0;
    List<String> result;

    List<String> choose = new ArrayList<>();

    /**
     * 官方-Hierholzer 算法
     * @param tickets
     * @return
     */
    public List<String> findItinerary2(List<List<String>> tickets) {
        for (List<String> ticket : tickets) {
            String src = ticket.get(0), dst = ticket.get(1);
            if (!map.containsKey(src)) {
                map.put(src, new PriorityQueue<String>());
            }
            map.get(src).offer(dst);
        }
        dfs("JFK");
        Collections.reverse(itinerary);
        return itinerary;
    }

    public void dfs(String curr) {
        while (map.containsKey(curr) && map.get(curr).size() > 0) {
            String tmp = map.get(curr).poll();
            dfs(tmp);
        }
        itinerary.add(curr);
    }

    Map<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();
    List<String> itinerary = new LinkedList<String>();

}
